package study.wy.linkedlist.single;

import java.util.Stack;

/**
 * 单向链表
 * @author wy
 */
public class SingleLinkedList<T> {

    private final SingleLinkedNote<T> head = new SingleLinkedNote<>(0,null);

    public SingleLinkedList() {
    }

    /**
     * 向链表中添加元素
     * @param data  添加的元素
     */
    public void add(SingleLinkedNote<T> data) {
        SingleLinkedNote<T> temp = head;
        /**
         * 找到末尾节点
         */
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = data;
    }

    /**
     * 展示链表所有数据
     */
    public void showList(){
        if (head.next == null) {
            System.out.println("空链表");
            return;
        }
        SingleLinkedNote<T> temp = head;
        while (temp.next != null) {
            temp = temp.next;
            System.out.println(temp);
        }
    }

    /**
     * 根据id向链表中添加数据，添加时会根据id大小自动排序，并且id相同时不可添加。
     * @param data  添加的元素
     */
    public void addById(SingleLinkedNote<T> data){
        SingleLinkedNote<T> temp = head;
        boolean isAdd = true;
        while (temp.next != null) {
            if (temp.next.getId() > data.getId()) {
                break;
            }
            if (temp.next.getId() == data.getId()) {
                isAdd = false;
                break;
            }
            temp = temp.next;
        }
        if (!isAdd) {
            System.out.println("已有此id元素，请勿重复添加");
            return;
        }
        data.next = temp.next;
        temp.next = data;
    }

    /**
     * 删除链表中指定id的元素
     * @param id    指定元素的id
     * @return      被删除的元素
     */
    public SingleLinkedNote<T> remove(int id) {
        SingleLinkedNote<T> temp = head;
        while (temp.next != null) {
            if (temp.next.getId() == id) {
                if (temp.next.next != null) {
                    temp.next = temp.next.next;
                } else {
                    temp.next = null;
                }
                return temp.next;
            }
            temp = temp.next;
        }
        System.out.println("链表中没有id为"+id+"的元素");
        return null;
    }

    /**
     * 更改链表中指定id的元素所存储的数据
     * @param id    指定元素的id
     * @param data  更改的数据
     */
    public void update(int id,T data) {
        SingleLinkedNote<T> temp = head;
        while (temp.next != null) {
            if (temp.next.getId() == id) {
                temp.next.setData(data);
                return;
            }
            temp = temp.next;
        }
        System.out.println("链表中没有id为"+id+"的元素");
    }

    /**
     * 获取链表中指定id值的数据
     * @param id    元素的id值
     * @return      指定元素
     */
    public SingleLinkedNote<T> get(int id){
        SingleLinkedNote<T> temp = head;
        while (temp.next != null) {
            if (temp.next.getId() == id) {
                return temp.next;
            }
            temp = temp.next;
        }
        System.out.println("链表中没有id为"+id+"的元素");
        return null;
    }

    /**
     * 获取链表中有效元素的个数
     * @return  有效元素的个数
     */
    public int size(){
        int size = 0;
        SingleLinkedNote<T> temp = head;
        while (temp.next != null) {
            size++;
            temp = temp.next;
        }
        return size;
    }

    /**
     * 获取链表中倒数第index个节点
     * @param index 倒数下标
     * @return      倒数第index个节点
     */
    public SingleLinkedNote<T> getBottom(int index){
        int size = size();
        if (index > size + 1 || index <= 0)
            return null;
        if (index == size + 1)
            return head;
        SingleLinkedNote<T> temp = head;
        int count = 0;
        while (temp.next != null) {
            temp = temp.next;
            count++;
            if (count + index == size + 1)
                return temp;
        }
        return null;
    }

    /**
     * 将此链表中所有节点反转的另一种方法
     */
    public void anotherReverseList(){
        SingleLinkedNote<T> newNote = new SingleLinkedNote<T>(0,null);
        SingleLinkedNote<T> tempHead = head.next;
        while (tempHead != null) {
            head.next = tempHead.next;
            tempHead.next = newNote.next;
            newNote.next = tempHead;
            tempHead = head.next;
        }
        head.next = newNote.next;
    }

    /**
     * 将此链表中所有节点反转
     */
    public void reverseList(){
        int size = size();
        for (int i = 1; i < size; i++) {
            SingleLinkedNote<T> bottom = getBottom(1);
            SingleLinkedNote<T> bottomSecond = getBottom(2);
            addIndex(i,bottom);
            bottomSecond.next = null;
        }
    }

    /**
     * 向链表中指定位置添加元素
     * @param index 指定的位置
     * @param data  添加的元素
     */
    public void addIndex(int index, SingleLinkedNote<T> data){
        int size = size();
        if (head.next == null)
            head.next = data;
        if (index <= 0 || index > size + 1)
            return;
        int count  = 0;
        SingleLinkedNote<T> temp = head;
        while (temp.next != null){
            if (count == index - 1) {
                data.next = temp.next;
                temp.next = data;
                return;
            }
            temp = temp.next;
            count++;
        }
    }

    /**
     * 倒叙打印链表
     */
    public void showReverseList(){
        int size = size();
        if (size == 0){
            System.out.println("空链表");
        }
        for (int i = 1; i <= size; i++) {
            System.out.println(getBottom(i));
        }
    }

    /**
     * 利用栈倒叙打印链表
     */
    public void showReverseListForStack() {
        if (head.next == null) {
            System.out.println("空链表");
            return;
        }
        Stack<SingleLinkedNote<T>> stack = new Stack<>();
        SingleLinkedNote<T> temp = head;
        while (temp.next != null) {
            stack.push(temp.next);
            temp = temp.next;
        }
        int size = stack.size();
        for (int i = 0; i < size; i++) {
            System.out.println(stack.pop());
        }
    }

    /**
     * 向有序链表中添加一条链表，加完之后仍然有序
     * @param list  添加的链表
     */
    public void addByIdForList(SingleLinkedList<T> list){
        if (list == null || list.size() == 0)
            return;
        while (list.head.next != null) {
            SingleLinkedNote<T> temp = list.head.next;
            list.head.next = list.head.next.next;
            addById(temp);
        }
    }
}
